package sol.leetcode;

import def.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Unique Binary Search Trees II
 */
public class Issue095 {
    public List<TreeNode> generateTrees(int n) {
        if (n==0)
            return new ArrayList<TreeNode>();
        return generateTrees(1, n + 1);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        for (int i = start; i < end; ++i) {
            List<TreeNode> lefts = generateTrees(start, i);
            List<TreeNode> rights = generateTrees(i + 1, end);
            for (TreeNode l : lefts) {
                for (TreeNode r : rights) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        if (res.size()==0)
            res.add(null);
        return res;
    }

    public static void main(String[] args) {
        Issue095 sol = new Issue095();
        List<TreeNode> res = sol.generateTrees(0);
        System.out.println(res.size());
    }
}
